package com.zxlfysj.search;

/**
 * 二分查找
 * @author yangshujing
 * @create 2020-08-18 22:39
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 8, 11, 13, 15, 17};
        //System.out.println(binarySearch(arr, 0, arr.length - 1, -2));
        System.out.println(binarySearch(arr, 17));

    }

    /**
     *
     * @param arr   数组
     * @param left  左边的索引
     * @param right 右边的索引
     * @param key   要查找的值
     * @return  返回数组下标，返回-1表示没有找到
     */
    public static int binarySearch(int[] arr, int left, int right, int key) {
       if(left > right) {
           return -1;
       }
       int mid = (left + right) / 2;
       if(arr[mid] == key) {
           return mid;
       } else if(arr[mid] > key) {
           //向左递归
            return binarySearch(arr, left, mid - 1, key);
       } else {
           //向右递归
            return binarySearch(arr, mid + 1, right, key);
       }

    }

    /**
     *  二分查找非递归实现
     * @param arr   待查找的数组
     * @param target    查找的数
     * @return  返回数组下标，返回-1表示没有找到
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while(left <= right) {
            mid = (left + right) / 2;
            if(arr[mid] > target) {
                right = mid - 1;
            } else if(arr[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;

    }
}
